package main

// 75. 颜色分类
func main() {
	//nums := []int{2, 0, 2, 1, 1, 0}
	//nums := []int{2, 0, 1}
	nums := []int{1, 2, 0}
	sortColors(nums)
	for _, num := range nums {
		print(num, "-")
	}
}

func sortColors(nums []int) {
	// 一遍扫描，左边放0，右边放2，再加个ptr扫描，小于右侧指针
	// 指针指的位置，是合格的数字
	left, right := 0, len(nums)-1
	ptr := 0

	for ptr <= right {
		if nums[ptr] == 0 { // 左侧置换
			nums[left], nums[ptr] = nums[ptr], nums[left]
			left++
			if ptr < left {
				ptr++
			}
		} else if nums[ptr] == 2 { // 右侧置换
			nums[right], nums[ptr] = nums[ptr], nums[right]
			right--
		} else if nums[ptr] == 1 {
			ptr++
		}
	}

	return
}

/**
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？
*/
